/**
 * @param {number[]} nums
 * @param {number[]} l
 * @param {number[]} r
 * @return {boolean[]}
 */
export var checkArithmeticSubarrays = function (nums, l, r) {
  const ans = []
  for (let i = 0; i < l.length; i++) {
    ans.push(check2(nums, l[i], r[i]))
  }
  return ans
}

const qickSort = arr => {
  if (arr.length < 2) return arr
  let pivot = arr[arr.length >> 1]
  let left = []
  let right = []
  for (let i = 0; i < arr.length; i++) {
    if (i === arr.length >> 1) continue
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...qickSort(left), pivot, ...qickSort(right)]
}

export function check(nums, l, r) {
  const arr = qickSort(nums.slice(l, r + 1))
  for (let i = 0; i < r - l; i++) {
    if (arr[i + 1] - arr[i] !== arr[1] - arr[0]) return false
  }
  return true
}

export function check2(nums, l, r) {
  const n = r + 1 - l
  if (n === 2) return true
  let [min, max] = [Infinity, -Infinity]
  const set = new Set()
  for (let i = l; i < r + 1; i++) {
    set.add(nums[i])
    min = Math.min(min, nums[i])
    max = Math.max(max, nums[i])
  }
  if ((max - min) % (n - 1)) return false
  const d = (max - min) / (n - 1) // 公差
  for (let i = 1; i < n; i++) {
    if (!set.has(min + i * d)) return false
  }
  return true
}
